class BSTItem {
    key: any;
    left: any = null;
    right: any = null;
    constructor(key: any) {
      this.key = key;
    }
  }
  export  default class BinarySearchTree {
    root: any = null;
    count: number = 0;
    public insert(key: number) {
      var newNode = new BSTItem(key);
      var isFinish: boolean | undefined = true;
      if (this.root === null) {
        this.root = newNode;
        isFinish = true;
      } else {
        isFinish = this.insertNode(this.root, newNode) || true;
      }
      isFinish && (this.count += 1);
      return !!isFinish
    }
    // 私有方法 插入节点
    private insertNode(node: BSTItem, newNode: BSTItem) {
      if (newNode.key > node.key) {
        if (node.right === null) {
          node.right = newNode
        } else {
          this.insertNode(node.right, newNode)
        }
      } else if (newNode.key < node.key) {
        if (node.left === null) {
          node.left = newNode
        } else {
          this.insertNode(node.left, newNode)
        }
      } else {
        return false;
      }
    }
    // 遍历抽象递归方法
    private bstOrder(node: BSTItem, arr: Array<number>, type: string): void {
      if (node !== null) {
        type === 'pre' && arr.push(node.key);
        this.bstOrder(node.left, arr, type)
        type === 'mid' && arr.push(node.key);
        this.bstOrder(node.right, arr, type)
        type === 'post' && arr.push(node.key);
      }
    }
    // 先序遍历
    public preorderTraversal(node?:any): string {
      var node = node || this.root
      var arr: Array<number> = [];
      if (node === null) {
        return ''
      } else {
        this.bstOrder(node, arr, 'pre')
      }
      return arr.join(',')
    }
  
    // 中序遍历
    public midorderTraversal(): string {
      var arr: Array<number> = [];
      if (this.root === null) {
        return ''
      } else {
        this.bstOrder(this.root, arr, 'mid')
      }
      return arr.join(',')
    }
    // 后序遍历
    public postorderTraversal(node?:any): string {
      var node = node || this.root
      var arr: Array<number> = [];
      if (node === null) {
        return ''
      } else {
        this.bstOrder(node, arr, 'post')
      }
      return arr.join(',')
    }
    // 寻找最大值
    public min(): any {
      if (this.root === null) {
        return null
      } else {
        var node = this.root;
        while (node.left) {
          node = node.left
        }
        return node.key
      }
    }
    // 后序遍历
    public max(): any {
      if (this.root === null) {
        return null
      } else {
        var node = this.root;
        while (node.right) {
          node = node.right
        }
        return node.key
      }
    }
    // 搜索
    public search(key: number): boolean {
      var node = this.root
      while (node !== null) {
        if (key < node.key) {
          node = node.left
        } else if (key > node.key) {
          node = node.right
        } else {
          return true
        }
      }
      return false
    }
    // 删除节点
    public remove(key: number): boolean {
      var current = this.root;
      var parent = this.root;
      var child: any = null;
      while (key !== current.key) {
        if (key < current.key) {
          parent = current;
          child = 'left'
          current = current.left
        } else {
          parent = current;
          child = 'right'
          current = current.right
        }
        if (current === null) return false
      }
      // 分三种情况 
      // 1,叶子结点
      if (current.left === null && current.right === null) {
        if (current === this.root) {
          this.root = null;
        } else {
          parent[child] = null;
        }
      }
      // 2,单个节点
      if (current.left && current.right === null) {
        if (current === this.root) {
          this.root = current.left;
        } else {
          parent.left = current.left
        }
      } else if (current.right && current.left === null) {
        if (current === this.root) {
          this.root = current.right;
        } else {
          if (current.right.key < parent.key) {
            parent.left = current.right
          } else {
            parent.right = current.right
          }
        }
      }
      // 3,有两个节点的 比较复杂 
      if (current.left && current.right) {
        var leftArr = this.preorderTraversal(current.left).split(',')
        var rightArr = this.preorderTraversal(current.right).split(',')
        if (current === this.root) {
          var rootKey = leftArr.length > rightArr.length?current.left.key:current.right.key;
          this.root = null;
          this.insert(rootKey)
          leftArr.forEach(item=>{
            this.insert(item)
          })
          rightArr.forEach(item=>{
            this.insert(item)
          })
        } else {
          parent[child] = null;
          leftArr.forEach(item=>{
            this.insert(item)
          })
          rightArr.forEach(item=>{
            this.insert(item)
          })
        }
      }
      return true
    }
  }

